While addition requires a direct merge of terms, the operation of subtraction, $P(x) - R(x)$, is immediately reducible to the addition problem by exploiting a simple algebraic equivalence.
- Polynomial subtraction is implemented by performing $P(x) + (-R(x))$.
- The core difference is a pre-processing step where the linked list representing the subtrahend, $R(x)$, is traversed once to negate every coefficient.
- Procedure for $P(x) - R(x)$:
- 1. Negation: Traverse the linked list $R(x)$, and for every `Polynomial_Term` node, multiply the coefficient by $\mathbf{-1}$. This takes $O(m)$ time.
- 2. Addition Reuse: Execute the standard $O(n+m)$ polynomial addition algorithm, using $P(x)$ and the newly negated list, $-R(x)$.
- Since the negation step is performed *before* the merge and takes only $O(m)$ time, the total time complexity remains $O(n+m)$.
Complexity Analysis
The subtraction $P(x) - R(x)$ is achieved by negating $R(x)$ and then performing addition $P(x) + (-R(x))$.
| Operation | Complexity | Reason |
|---|---|---|
| Negating $R(x)$ | $O(m)$ | Single traversal of $m$ nodes. |
| Addition $P(x) + (-R(x))$ | $O(n+m)$ | Standard merge operation. |
| Total Subtraction Time | $O(n+m)$ | Dominated by the addition/merge step. |